package wangyi;

public class Main4 {

    public int minSailCost (int[][] input) {
        // write code here
        if (input == null || input[0] == null){
            return -1;
        }
        int xLen = input.length;
        int yLen = input[0].length;
        int[][] dp = new int[xLen][yLen];
        //进行初始化
        for (int i = 1; i < yLen; i++){
            if (input[0][i] == 2){
                dp[0][i] = Integer.MAX_VALUE;
                continue;
            } else {
                if (input[0][i] == 0){
                    dp[0][i] = dp[0][i - 1] == Integer.MAX_VALUE?Integer.MAX_VALUE:dp[0][i - 1] + 2;
                } else {
                    dp[0][i] = dp[0][i - 1] == Integer.MAX_VALUE?Integer.MAX_VALUE:dp[0][i - 1] + 1;
                }
            }
        }
        for (int i = 1; i < xLen; i++){
            if (input[i][0] == 2){
                dp[i][0] = Integer.MAX_VALUE;
                continue;
            } else {
                if (input[i][0] == 0){
                    dp[i][0] = Math.min(dp[i - 1][0] == Integer.MAX_VALUE?Integer.MAX_VALUE:dp[i - 1][0] + 2, dp[i][0]);
                } else {
                    dp[i][0] = Math.min(dp[i - 1][0] == Integer.MAX_VALUE?Integer.MAX_VALUE:dp[i - 1][0] + 1, dp[i][0]);
                }
            }
        }
        for (int i = 1; i < xLen; i++){
            for (int j  = 1; j < yLen; j++){
                if (input[i][j] == 2){
                    dp[i][j] = Integer.MAX_VALUE;
                    continue;
                } else {
                    if (input[i][j] == 0){
                        dp[i][j] = Math.min(dp[i][j - 1] == Integer.MAX_VALUE?Integer.MAX_VALUE:dp[i][j - 1] + 2, dp[i - 1][j] == Integer.MAX_VALUE?Integer.MAX_VALUE:dp[i - 1][j] + 2);
                    } else {
                        dp[i][j] = Math.min(dp[i][j - 1] == Integer.MAX_VALUE?Integer.MAX_VALUE:dp[i][j - 1] + 1, dp[i - 1][j] == Integer.MAX_VALUE?Integer.MAX_VALUE:dp[i - 1][j] + 1);
                    }
                }
            }
        }
        return dp[xLen - 1][yLen - 1] == Integer.MAX_VALUE? -1:dp[xLen - 1][yLen - 1];
    }
}
